﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace SmartMathLibrary
{
    /// <summary>
    /// This class provides the splitting of a natural number in two factors by using
    /// the algorithm of Lehman.
    /// </summary>
    [Serializable]
    public class LehmanNumberFactorizer : AbstractNumberFactorizer
    {
        /// <summary>
        /// Initializes a new instance of the <see cref="LehmanNumberFactorizer"/> class.
        /// </summary>
        /// <param name="number">The number to factorize.</param>
        public LehmanNumberFactorizer(UInt64 number)
            : base(number)
        {
        }

        /// <summary>
        /// Factorizes the specified number by using the algorithm of Lehman.
        /// </summary>
        /// <returns>The factors of the number.</returns>
        public override ulong[] Factorize()
        {
            double n = this.Number;
            ulong[] result = new ulong[2];

            result[0] = this.Number;
            result[1] = 1;

            for (int k = 1; k <= ExtendedMath.Root(n, 3); k++)
            {
                for (double x = (Math.Sqrt(4 * k * n));
                     x <= (Math.Sqrt(4 * k * n) + ((ExtendedMath.Root(n, 6)) / (4 * Math.Sqrt(k))));
                     x++)
                {
                    double y = Math.Pow(x, 2) - (4 * k * n);

                    if (ExtendedMath.IsSquareNumber(y))
                    {
                        result[0] = ExtendedMath.GCD((ulong) (x + Math.Sqrt(y)), this.Number);
                        result[1] = this.Number / result[0];
                        break;
                    }
                }
            }

            return result;
        }
    }
}